#include <iostream>

using namespace std;

struct TreeNode 
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) 
		:val(x)
		,left(NULL)
		,right(NULL) 
	{}
	TreeNode(int x, TreeNode* _left, TreeNode* _right)
		:val(x)
		,left(_left)
		,right(_right)
	{}

};
class Solution 
{
public:
	TreeNode* pre = nullptr, * head = nullptr;

	TreeNode* Convert(TreeNode* pRootOfTree)
	{
		if (!pRootOfTree)
			return nullptr;

		Convert(pRootOfTree->left);
		if (!pre)
		{
			pre = pRootOfTree;
			head = pRootOfTree;
		}
		else
		{
			pRootOfTree->left = pre;
			pre->right = pRootOfTree;
			pre = pRootOfTree;
		}
		Convert(pRootOfTree->right);
		return head;
	}
};

int main()
{
	TreeNode* F = new TreeNode(16);
	TreeNode* E = new TreeNode(12);
	TreeNode* D = new TreeNode(8);
	TreeNode* C = new TreeNode(4);
	TreeNode* B = new TreeNode(14, E, F);
	TreeNode* A = new TreeNode(6, C, D);
	TreeNode* root = new TreeNode(10, A, B);

	Solution xz;
	TreeNode* head = xz.Convert(root);

	while (head)
	{
		cout << head->val << ' ';
		head = head->right;
	}

	return 0;
}